package Sort;

import java.util.Arrays;
import java.util.Stack;

public class QuickSort {
    public void operation(int[] arr) {
        operation(arr, 0, arr.length - 1);
    }

    //三数取中 + 直接插入排序
    public void operation(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        if (right - left + 1 <= 7) {
            for (int i = left + 1; i <= right; i++) {
                int tmp = arr[i];
                int j = i - 1;
                for (; j >= left; j--) {
                    if (arr[j] > tmp) {
                        arr[j + 1] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j + 1] = tmp;
            }
            return;
        }

        int midNumIndex = getMidNumIndex(arr, left, right, (left + right) / 2);

        swap(arr, left, midNumIndex);

        int prev = quick2(arr, left, right);

        operation(arr, left, prev - 1);
        operation(arr, prev + 1, right);
    }

    private static int getMidNumIndex(int[] arr, int left, int right, int mid) {
        if (arr[left] < arr[right]) {
            if (arr[left] > arr[mid]) {
                return left;
            } else if (arr[right] > arr[mid]) {
                return mid;
            } else {
                return right;
            }
        } else {
            if (arr[left] < arr[mid]) {
                return left;
            } else if (arr[right] > arr[mid]) {
                return right;
            } else {
                return mid;
            }
        }
    }

    public int quick(int[] arr, int left, int right) {
        int tmp = arr[left];
        int tmpLeft = left;

        while (left < right) {
            while (right > left && arr[right] >= tmp) {
                right--;
            }
            while (right > left && arr[left] <= tmp) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, tmpLeft, left);

        return left;
    }

    public int quick2(int[] arr, int left, int right) {
        int tmp = arr[left];
        int tmpLeft = left;

        while (left < right) {
            while (right > left && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            while (right > left && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];

        }
        arr[left] = tmp;

        return left;
    }

    //非递归快速排序
    public void  operationNor(int[] arr, int left, int right) {
        Stack<Integer> stack = new Stack<>();

        int prev = quick2(arr, left, right);

        if (prev > left + 1) {
            stack.push(left);
            stack.push(prev - 1);
        }
        if (prev < right - 1) {
            stack.push(prev + 1);
            stack.push(right);
        }

        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            prev = quick2(arr, left, right);
            if (prev > left + 1) {
                stack.push(left);
                stack.push(prev - 1);
            }
            if (prev < right - 1) {
                stack.push(prev + 1);
                stack.push(right);
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1};

        QuickSort quickSort = new QuickSort();
        quickSort.operationNor(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
